#include "../common/AVLTreeNode.h"

extern AVLTreeNode* rotate(AVLTreeNode*);

/* 平衡二叉搜索树递归删除结点 */
AVLTreeNode* remove(AVLTreeNode* node, int val) {
    if (node == nullptr)
        return nullptr;
    if (val < node->val)
        node->left = remove(node->left, val);
    else if (val > node->val)
        node->right = remove(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            AVLTreeNode* child = node->left != nullptr ? node->left : node->right;
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            else {
                delete node;
                node = child;
            }
        } else {
            AVLTreeNode* temp = getInOrderNext(node->right);
            int tempVal = temp->val;
            node->right = remove(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node);
    node = rotate(node);
    return node;
}

/* 获取中序遍历中的下一个结点（仅适用于 root 有左子结点的情况） */
AVLTreeNode* getInOrderNext(AVLTreeNode* node) {
    if (node == nullptr)
        return node;
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}
